package algo.graph;

import ds.adt.Graph;

public class TwoColor {

	private boolean[] marked;
	private boolean color[];
	private boolean isTwoColorable;

	public TwoColor(Graph g) {
		this.marked = new boolean[g.V()];
		this.color = new boolean[g.V()];
		this.isTwoColorable = true;

		for (int s = 0; s < g.V(); s++) {
			if (!marked[s]) {
				dfs(g, s);
			}
		}
	}

	/**
	 * Does DFS. While searching, assigns a color to a vertex different then its
	 * parent. When backtracking if the color of the child and parent vertices
	 * are same then the graph is not bipartite otherwise it is.
	 * 
	 * 
	 * @param g
	 * @param v
	 */
	private void dfs(Graph g, int v) {
		marked[v] = true;
		for (int w : g.adj(v)) {
			if (!marked[w]) {
				color[w] = !color[v];
				dfs(g, w);
			} else if (color[w] == color[v]) {
				isTwoColorable = false;
			}
		}
	}

	public boolean isBipartite() {
		return isTwoColorable;
	}

	public static void main(String[] args) {

		Graph g = new Graph(5);
		g.addEdge(0, 1);
		g.addEdge(1, 2);
		// g.addEdge(2, 0);
		g.addEdge(0, 3);
		g.addEdge(0, 4);

		TwoColor tc = new TwoColor(g);
		System.out.println("Is Graph bipartite ? " + tc.isBipartite());

	}

}
